#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 2475. 数组中不等三元组的数目
class Solution1
{
public:
    int unequalTriplets(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());
        int start = 0, n = nums.size(), ret = 0;
        for(int i = 0; i < n - 1; ++i)
        {
            if(nums[i] != nums[i + 1])
            {
                ret += start * (i + 1 - start) * (n - i - 1);
                start = i + 1; // start 表示前一部分数的个数
            }
        }
        return ret;
    }
};


struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

// 二叉搜索树最近节点查询
class Solution2
{
public:
    vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) 
    {
        vector<int> v = {-1};
        function<void(TreeNode*)> dfs = [&](TreeNode* node){
            if(node == nullptr) return;

            dfs(node->left);
            v.push_back(node->val);
            dfs(node->right);
        };

        dfs(root);
        v.push_back(1000001);

        vector<vector<int>> ret;
        for(int q : queries)
        {
            // index 是第一个大于等于 q 的元素的下标
            int index = lower_bound(v.begin(), v.end(), q) - v.begin();
            // -1 1 2 4 6 9 13 14 15 1000001
            // q=2：index=2
            // q=5：index=4
            if(v[index] == q) ret.push_back({q, q});
            else if(v[index] > q && v[index] != 1000001) ret.push_back({v[index - 1], v[index]});
            else ret.push_back({v[index - 1], -1});
        }
        return ret;
    }
};

// 2477. 到达首都的最少油耗
class Solution3
{
public:
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) 
    {
        int n = roads.size() + 1;
        vector<vector<int>> g(n);
        for(auto& e : roads)
        {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }  

        long long ret = 0;
        function<int(int, int)> dfs = [&](int x, int fa)
        {
            int size = 1;
            for(int y : g[x])
            {
                if(y != fa) size += dfs(y, x);
            }
            if(x != 0) ret += (size + seats - 1) / seats;
            return size;
        };
        dfs(0, -1);

        return ret;
    }
};

// 将字符串分割成值不超过 K 的子字符串
class Solution4
{
public:
    int minimumPartition(string s, int k) 
    {
        int ret = 1;
        long long tmp = 0;
        for(char digit : s)
        {
            digit -= '0';
            if(digit > k) return -1;
            tmp = tmp * 10 + digit;
            if(tmp > k)
            {
                ++ret;
                tmp = digit;
            }
        }    
        return ret;
    }
};

// 2523. 范围内最接近的两个质数
const int MX = 1e6;
vector<int> primes;

int init = [](){
    bool np[MX + 1]{};
    for(int i = 2; i <= MX; ++i)
    {
        if(!np[i])
        {
            primes.push_back(i);
            /*
            for(long long j = (long long)i * i; j <= MX; j += i)
                np[j] = true;
            */
            for(int j = i; j <= MX / i; ++j) // 避免溢出的写法
                np[j * i] = true;
        }
    }

    primes.push_back(MX + 1);
    primes.push_back(MX + 1); // 保证下面的下标不会越界
    return 0;
}();

class Solution 
{
public:
    vector<int> closestPrimes(int left, int right) 
    {
        int p = -1, q = -1;
        int i = lower_bound(primes.begin(), primes.end(), left) - primes.begin();
        while(primes[i + 1] <= right)
        {
            if(p < 0 || primes[i + 1] - primes[i] < q - p)
            {
                p = primes[i];
                q = primes[i + 1];
            }
            ++i;
        }
        return {p, q};
    }
};

struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 92. 反转链表 II
class Solution 
{
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) 
    {
        // 申请哨兵位头节点，避免重复操作
        ListNode* newHead = new ListNode;
        newHead->next = head;
        ListNode* prev = newHead;
        for(int i = 0; i < left - 1; ++i)
        {
            prev = prev->next;
        }

        // 采用头插进行反转链表
        // cur 现在是待反转链表的第一个节点，反转后是链表的最后一个节点
        ListNode* cur = prev->next; 
        ListNode* rTail = cur; // 记录最后一个节点，后续用来连接
        ListNode* rHead = nullptr;
        ListNode* next = nullptr;
        for(int i = 0; i < right - left + 1; ++i)
        {
            next = cur->next;
            cur->next = rHead;
            prev->next = cur;
            rHead = cur;
            cur = next;
        }
        rTail->next = next;

        ListNode* ret = newHead->next;
        delete newHead;
        return ret;
    }
};